//
// Created by ASUS on 2022/5/31.
//
#include "stdio.h"
/*                */
void print_array(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
void insertion_sort(int unsorted_array[], int num_elements){
    int i,j,temp;
    for(i=1 ; i < num_elements;i++){
        if(unsorted_array[i-1]>unsorted_array[i]){
            temp = unsorted_array[i];
            for ( j = i-1; unsorted_array[j] > temp && j != -1; --j) {
                unsorted_array[j+1] = unsorted_array[j];
            }
            unsorted_array[j+1] = temp;
        }
        print_array(unsorted_array,num_elements);
    }
}
/*待排序的数组元素的编号从0开始到total_num_elements-1。
要求：
1.实现如下声明  的partition函数；永远选择low位置上的元素作为pivot支撑元素；在partition函数返回pivot支撑元素的位置之前，把unsorted_array里的所有元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出 之后换行。
2.递归实现如下声明的quick_sort函数；在每次递归时先处理左侧的子数组，再处理右侧的子数组；quick_sort必须调用partition函数获取pivot支撑元素的位置。
3.比如当输入的unsorted_array数组的元素依次为 3, 1, 2, 5, 4时，输出应该为：
2 1 3 5 4
1 2 3 5 4
1 2 3 4 5

*/
int partition(int L[], int low,  int  high, int total_num_elements){
 int pivot =L[low];
  int temp;
    while (low<high){
        while (low < high&& L[high] >= pivot){
            high--;
        }
        temp = L[low];
        L[low] = L[high];
        L[high] = temp;
        while (low <high && L[low] <= pivot ){
            low++;
        }
        temp = L[low];
        L[low] = L[high];
        L[high] = temp;
    }
    pivot = low;
    print_array(L,total_num_elements);
    return pivot;
};
void QSort(int L[], int low,  int  high, int total_num_elements){
   int pivot;
    if (low<high){
       pivot = partition(L,low,high,total_num_elements);
        QSort(L,low,pivot-1,total_num_elements);
        QSort(L,pivot+1,high,total_num_elements);
    }
}
/*
待排序的数组元素的编号从0开始到num_elements-1
要求：
1.实现如下声明的heap_sort函数。
2.在每次对已经建好的最大堆进行调整然后把当前根里的最大值放置到合适正确的位置之后、再次调整形成最大堆之前，把unsorted_array里的所有元素的值打印到标准输出，元素值之间仅用英文的空格分隔，每次输出之后换行。例如：
10 60 12 40 30 8 70
8 40 12 10 30 60 70
8 30 12 10 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
*/
void  build_heap(int unsorted_array[], int num_elements){
    int temp;
    for (int i = (num_elements+1)/2; i >= 0 ; --i) {
        if(unsorted_array[i-1] <  unsorted_array [2*i-1]){
            temp =  unsorted_array[2*i-1];
            unsorted_array[2*i-1] = unsorted_array[i-1];
            unsorted_array[i-1] = temp;
        }
        if(unsorted_array[i-1] <  unsorted_array [2*i]){
            temp =  unsorted_array[2*i];
            unsorted_array[2*i] = unsorted_array[i-1];
            unsorted_array[i-1] = temp;
        }
    }
}
void swap(int unsorted_array[],int a,int b){
    int temp;
    temp = unsorted_array[a];
    unsorted_array[a] = unsorted_array[b];
    unsorted_array[b] = temp;
}
void heap_sort(int unsorted_array[], int num_elements){
    for (int i = (num_elements+1)/2; i >= 0 ; --i) {
        if(unsorted_array[i-1] <  unsorted_array [2*i-1]){
            build_heap(unsorted_array,num_elements);
        }
        if(unsorted_array[i-1] <  unsorted_array [2*i]){
            build_heap(unsorted_array,num_elements);
        }
    }
    for (int i = num_elements-1; i >= 0; --i) {
        if(i >= 2) {
            if (unsorted_array[0] < unsorted_array[1]) {
                swap(unsorted_array, 0, 1);
            }
            if (unsorted_array[0] < unsorted_array[2]) {
                swap(unsorted_array, 0, 2);
            }
        }
        if(unsorted_array[0] > unsorted_array[i] ){
            swap(unsorted_array,0,i);
            print_array(unsorted_array,num_elements);
        }
    }
}
int main(){
   int a[7]  = {10,60,12,40,30,8,70};
   int size = 7;
    heap_sort(a,size);
}